home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 5 / Apprentice-Release5.iso / Source Code / Libraries / Berkeley DB 1.8.5a / hash / hash.c < prev    next >
Encoding:
Text File  |  1995-08-01  |  23.8 KB  |  861 lines  |  [TEXT/CWIE]
  1. /*-
  2.  * Copyright (c) 1990, 1993, 1994
  3.  *    The Regents of the University of California.  All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * Margo Seltzer.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  */
  36.  
  37. #if defined(LIBC_SCCS) && !defined(lint)
  38. static char sccsid[] = "@(#)hash.c    8.9 (Berkeley) 6/16/94";
  39. #endif /* LIBC_SCCS anapp[0], 0, bpages * sizeof(u_int32_t *));
  40.     }
  41.  
  42.     /* Initialize Buffer Manager */
  43.     if (info && info->cachesize)
  44.         __buf_init(hashp, info->cachesize);
  45.     else
  46.         __buf_init(hashp, DEF_BUFSIZE);
  47.  
  48.     hashp->new_file = new_table;
  49. #ifdef macintosh
  50.     hashp->save_file = file && ((flags & O_ACCMODE) == O_RDWR);
  51. #else
  52.     hashp->save_file = file && (hashp->flags & O_RDWR);
  53. #endif
  54.     hashp->cbucket = -1;
  55.     if (!(dbp = (DB *)malloc(sizeof(DB)))) {
  56.         save_errno = errno;
  57.         hdestroy(hashp);
  58.         errno = save_errno;
  59.         return (NULL);
  60.     }
  61.     dbp->internal = hashp;
  62.     dbp->close = hash_close;
  63.     dbp->del = hash_delete;
  64.     dbp->fd = hash_fd;
  65.     dbp->get = hash_get;
  66.     dbp->put = hash_put;
  67.     dbp->seq = hash_seq;
  68.     dbp->sync = hash_sync;
  69.     dbp->type = DB_HASH;
  70.  
  71. #ifdef DEBUG
  72.     (void)fprintf(stderr,
  73. "%s\n%s%x\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%x\n%s%x\n%s%d\n%s%d\n",
  74.         "init_htab:",
  75.         "TABLE POINTER   ", hashp,
  76.         "BUCKET SIZE     ", hashp->BSIZE,
  77.         "BUCKET SHIFT    ", hashp->BSHIFT,
  78.         "DIRECTORY SIZE  ", hashp->DSIZE,
  79.         "SEGMENT SIZE    ", hashp->SGSIZE,
  80.         "SEGMENT SHIFT   ", hashp->SSHIFT,
  81.         "FILL FACTOR     ", hashp->FFACTOR,
  82.         "MAX BUCKET      ", hashp->MAX_BUCKET,
  83.         "OVFL POINT         ", hashp->OVFL_POINT,
  84.         "LAST FREED      ", hashp->LAST_FREED,
  85.         "HIGH MASK       ", hashp->HIGH_MASK,
  86.         "LOW  MASK       ", hashp->LOW_MASK,
  87.         "NSEGS           ", hashp->nsegs,
  88.         "NKEYS           ", hashp->NKEYS);
  89. #endif
  90. #ifdef HASH_STATISTICS
  91.     hash_overflows = hash_accesses = hash_collisions = hash_expansions = 0;
  92. #endif
  93.     return (dbp);
  94.  
  95. error1:
  96.     if (hashp != NULL)
  97.         (void)close(hashp->fp);
  98.  
  99. error0:
  100.     free(hashp);
  101.     errno = save_errno;
  102.     return (NULL);
  103. }
  104.  
  105. static int
  106. hash_close(dbp)
  107.     DB *dbp;
  108. {
  109.     HTAB *hashp;
  110.     int retval;
  111.  
  112.     if (!dbp)
  113.         return (ERROR);
  114.  
  115.     hashp = (HTAB *)dbp->internal;
  116.     retval = hdestroy(hashp);
  117.     free(dbp);
  118.     return (retval);
  119. }
  120.  
  121. static int
  122. hash_fd(dbp)
  123.     const DB *dbp;
  124. {
  125.     HTAB *hashp;
  126.  
  127.     if (!dbp)
  128.         return (ERROR);
  129.  
  130.     hashp = (HTAB *)dbp->internal;
  131.     if (hashp->fp == -1) {
  132.         errno = ENOENT;
  133.         return (-1);
  134.     }
  135.     return (hashp->fp);
  136. }
  137.  
  138. /************************** LOCAL CREATION ROUTINES **********************/
  139. static HTAB *
  140. init_hash(hashp, file, info)
  141.     HTAB *hashp;
  142.     const char *file;
  143.     HASHINFO *info;
  144. {
  145.     struct stat statbuf;
  146.     int nelem;
  147.  
  148.     nelem = 1;
  149.     hashp->NKEYS = 0;
  150.     hashp->LORDER = BYTE_ORDER;
  151.     hashp->BSIZE = DEF_BUCKET_SIZE;
  152.     hashp->BSHIFT = DEF_BUCKET_SHIFT;
  153.     hashp->SGSIZE = DEF_SEGSIZE;
  154.     hashp->SSHIFT = DEF_SEGSIZE_SHIFT;
  155.     hashp->DSIZE = DEF_DIRSIZE;
  156.     hashp->FFACTOR = DEF_FFACTOR;
  157.     hashp->hash = __default_hash;
  158.     memset(hashp->SPARES, 0, sizeof(hashp->SPARES));
  159.     memset(hashp->BITMAPS, 0, sizeof (hashp->BITMAPS));
  160.  
  161.     /* Fix bucket size to be optimal for file system */
  162.     if (file != NULL) {
  163.         if (stat(file, &statbuf))
  164.             return (NULL);
  165.         hashp->BSIZE = statbuf.st_blksize;
  166.         hashp->BSHIFT = __log2(hashp->BSIZE);
  167.     }
  168.  
  169.     if (info) {
  170.         if (info->bsize) {
  171.             /* Round pagesize up to power of 2 */
  172.             hashp->BSHIFT = __log2(info->bsize);
  173.             hashp->BSIZE = 1 << hashp->BSHIFT;
  174.             if (hashp->BSIZE > MAX_BSIZE) {
  175.                 errno = EINVAL;
  176.                 return (NULL);
  177.             }
  178.         }
  179.         if (info->ffactor)
  180.             hashp->FFACTOR = info->ffactor;
  181.         if (info->hash)
  182.             hashp->hash = info->hash;
  183.         if (info->nelem)
  184.             nelem = info->nelem;
  185.         if (info->lorder) {
  186.             if (info->lorder != BIG_ENDIAN &&
  187.                 info->lorder != LITTLE_ENDIAN) {
  188.                 errno = EINVAL;
  189.                 return (NULL);
  190.             }
  191.             hashp->LORDER = info->lorder;
  192.         }
  193.     }
  194.     /* init_htab should destroy the table and set errno if it fails */
  195.     if (init_htab(hashp, nelem))
  196.         return (NULL);
  197.     else
  198.         return (hashp);
  199. }
  200. /*
  201.  * This calls alloc_segs which may run out of memory.  Alloc_segs will destroy
  202.  * the table and set errno, so we just pass the error information along.
  203.  *
  204.  * Returns 0 on No Error
  205.  */
  206. static int
  207. init_htab(hashp, nelem)
  208.     HTAB *hashp;
  209.     int nelem;
  210. {
  211.     register int nbuckets, nsegs;
  212.     int l2;
  213.  
  214.     /*
  215.      * Divide number of elements by the fill factor and determine a
  216.      * desired number of buckets.  Allocate space for the next greater
  217.      * power of two number of buckets.
  218.      */
  219.     nelem = (nelem - 1) / hashp->FFACTOR + 1;
  220.  
  221.     l2 = __log2(MAX(nelem, 2));
  222.     nbuckets = 1 << l2;
  223.  
  224.     hashp->SPARES[l2] = l2 + 1;
  225.     hashp->SPARES[l2 + 1] = l2 + 1;
  226.     hashp->OVFL_POINT = l2;
  227.     hashp->LAST_FREED = 2;
  228.  
  229.     /* First bitmap page is at: splitpoint l2 page offset 1 */
  230.     if (__ibitmap(hashp, OADDR_OF(l2, 1), l2 + 1, 0))
  231.         return (-1);
  232.  
  233.     hashp->MAX_BUCKET = hashp->LOW_MASK = nbuckets - 1;
  234.     hashp->HIGH_MASK = (nbuckets << 1) - 1;
  235.     hashp->HDRPAGES = ((MAX(sizeof(HASHHDR), MINHDRSIZE) - 1) >>
  236.         hashp->BSHIFT) + 1;
  237.  
  238.     nsegs = (nbuckets - 1) / hashp->SGSIZE + 1;
  239.     nsegs = 1 << __log2(nsegs);
  240.  
  241.     if (nsegs > hashp->DSIZE)
  242.         hashp->DSIZE = nsegs;
  243.     return (alloc_segs(hashp, nsegs));
  244. }
  245.  
  246. /********************** DESTROY/CLOSE ROUTINES ************************/
  247.  
  248. /*
  249.  * Flushes any changes to the file if necessary and destroys the hashp
  250.  * structure, freeing all allocated space.
  251.  */
  252. static int
  253. hdestroy(hashp)
  254.     HTAB *hashp;
  255. {
  256.     int i, save_errno;
  257.  
  258.     save_errno = 0;
  259.  
  260. #ifdef HASH_STATISTICS
  261.     (void)fprintf(stderr, "hdestroy: accesses %ld collisions %ld\n",
  262.         hash_accesses, hash_collisions);
  263.     (void)fprintf(stderr, "hdestroy: expansions %ld\n",
  264.         hash_expansions);
  265.     (void)fprintf(stderr, "hdestroy: overflows %ld\n",
  266.         hash_overflows);
  267.     (void)fprintf(stderr, "keys %ld maxp %d segmentcount %d\n",
  268.         hashp->NKEYS, hashp->MAX_BUCKET, hashp->nsegs);
  269.  
  270.     for (i = 0; i < NCACHED; i++)
  271.         (void)fprintf(stderr,
  272.             "spares[%d] = %d\n", i, hashp->SPARES[i]);
  273. #endif
  274.     /*
  275.      * Call on buffer manager to free buffers, and if required,
  276.      * write them to disk.
  277.      */
  278.     if (__buf_free(hashp, 1, hashp->save_file))
  279.         save_errno = errno;
  280.     if (hashp->dir) {
  281.         free(*hashp->dir);    /* Free initial segments */
  282.         /* Free extra segments */
  283.         while (hashp->exsegs--)
  284.             free(hashp->dir[--hashp->nsegs]);
  285.         free(hashp->dir);
  286.     }
  287.     if (flush_meta(hashp) && !save_errno)
  288.         save_errno = errno;
  289.     /* Free Bigmaps */
  290.     for (i = 0; i < hashp->nmaps; i++)
  291.         if (hashp->mapp[i])
  292.             free(hashp->mapp[i]);
  293.  
  294.     if (hashp->fp != -1)
  295.         (void)close(hashp->fp);
  296.  
  297.     free(hashp);
  298.  
  299.     if (save_errno) {
  300.         errno = save_errno;
  301.         return (ERROR);
  302.     }
  303.     return (SUCCESS);
  304. }
  305. /*
  306.  * Write modified pages to disk
  307.  *
  308.  * Returns:
  309.  *     0 == OK
  310.  *    -1 ERROR
  311.  */
  312. static int
  313. hash_sync(dbp, flags)
  314.     const DB *dbp;
  315.     u_int32_t flags;
  316. {
  317.     HTAB *hashp;
  318.  
  319.     if (flags != 0) {
  320.         errno = EINVAL;
  321.         return (ERROR);
  322.     }
  323.  
  324.     if (!dbp)
  325.         return (ERROR);
  326.  
  327.     hashp = (HTAB *)dbp->internal;
  328.     if (!hashp->save_file)
  329.         return (0);
  330.     if (__buf_free(hashp, 0, 1) || flush_meta(hashp))
  331.         return (ERROR);
  332.     hashp->new_file = 0;
  333.     return (0);
  334. }
  335.  
  336. /*
  337.  * Returns:
  338.  *     0 == OK
  339.  *    -1 indicates that errno should be set
  340.  */
  341. static int
  342. flush_meta(hashp)
  343.     HTAB *hashp;
  344. {
  345.     HASHHDR *whdrp;
  346. #if BYTE_ORDER == LITTLE_ENDIAN
  347.     HASHHDR whdr;
  348. #endif
  349.     int fp, i, wsize;
  350.  
  351.     if (!hashp->save_file)
  352.         return (0);
  353.     hashp->MAGIC = HASHMAGIC;
  354.     hashp->VERSION = HASHVERSION;
  355.     hashp->H_CHARKEY = hashp->hash(CHARKEY, sizeof(CHARKEY));
  356.  
  357.     fp = hashp->fp;
  358.     whdrp = &hashp->hdr;
  359. #if BYTE_ORDER == LITTLE_ENDIAN
  360.     whdrp = &whdr;
  361.     swap_header_copy(&hashp->hdr, whdrp);
  362. #endif
  363.     if ((lseek(fp, (off_t)0, SEEK_SET) == -1) ||
  364.         ((wsize = DB_write(fp, whdrp, sizeof(HASHHDR))) == -1))
  365.         return (-1);
  366.     else
  367.         if (wsize != sizeof(HASHHDR)) {
  368.             errno = EFTYPE;
  369.             hashp->errno = errno;
  370.             return (-1);
  371.         }
  372.     for (i = 0; i < NCACHED; i++)
  373.         if (hashp->mapp[i])
  374.             if (__put_page(hashp, (char *)hashp->mapp[i],
  375.                 hashp->BITMAPS[i], 0, 1))
  376.                 return (-1);
  377.     return (0);
  378. }
  379.  
  380. /*******************************SEARCH ROUTINES *****************************/
  381. /*
  382.  * All the access routines return
  383.  *
  384.  * Returns:
  385.  *     0 on SUCCESS
  386.  *     1 to indicate an external ERROR (i.e. key not found, etc)
  387.  *    -1 to indicate an internal ERROR (i.e. out of memory, etc)
  388.  */
  389. static int
  390. hash_get(dbp, key, data, flag)
  391.     const DB *dbp;
  392.     const DBT *key;
  393.     DBT *data;
  394.     u_int32_t flag;
  395. {
  396.     HTAB *hashp;
  397.  
  398.     hashp = (HTAB *)dbp->internal;
  399.     if (flag) {
  400.         hashp->errno = errno = EINVAL;
  401.         return (ERROR);
  402.     }
  403.     return (hash_access(hashp, HASH_GET, (DBT *)key, data));
  404. }
  405.  
  406. static int
  407. hash_put(dbp, key, data, flag)
  408.     const DB *dbp;
  409.     DBT *key;
  410.     const DBT *data;
  411.     u_int32_t flag;
  412. {
  413.     HTAB *hashp;
  414.  
  415.     hashp = (HTAB *)dbp->internal;
  416.     if (flag && flag != R_NOOVERWRITE) {
  417.         hashp->errno = errno = EINVAL;
  418.         return (ERROR);
  419.     }
  420.     if ((hashp->flags & O_ACCMODE) == O_RDONLY) {
  421.         hashp->errno = errno = EPERM;
  422.         return (ERROR);
  423.     }
  424.     return (hash_access(hashp, flag == R_NOOVERWRITE ?
  425.         HASH_PUTNEW : HASH_PUT, (DBT *)key, (DBT *)data));
  426. }
  427.  
  428. static int
  429. hash_delete(dbp, key, flag)
  430.     const DB *dbp;
  431.     const DBT *key;
  432.     u_int32_t flag;        /* Ignored */
  433. {
  434.     HTAB *hashp;
  435.  
  436.     hashp = (HTAB *)dbp->internal;
  437.     if (flag && flag != R_CURSOR) {
  438.         hashp->errno = errno = EINVAL;
  439.         return (ERROR);
  440.     }
  441.     if ((hashp->flags & O_ACCMODE) == O_RDONLY) {
  442.         hashp->errno = errno = EPERM;
  443.         return (ERROR);
  444.     }
  445.     return (hash_access(hashp, HASH_DELETE, (DBT *)key, NULL));
  446. }
  447.  
  448. /*
  449.  * Assume that hashp has been set in wrapper routine.
  450.  */
  451. #ifdef macintosh
  452. static int
  453. hash_access(HTAB *hashp, ACTION action, DBT * key, DBT * val)
  454. #else
  455. static int
  456. hash_access(hashp, action, key, val)
  457.     HTAB *hashp;
  458.     ACTION action;
  459.     DBT *key, *val;
  460. #endif
  461. {
  462.     register BUFHEAD *rbufp;
  463.     BUFHEAD *bufp, *save_bufp;
  464.     register u_int16_t *bp;
  465.     register int n, ndx, off, size;
  466.     register char *kp;
  467.     u_int16_t pageno;
  468.  
  469. #ifdef HASH_STATISTICS
  470.     hash_accesses++;
  471. #endif
  472.  
  473.     off = hashp->BSIZE;
  474.     size = key->size;
  475.     kp = (char *)key->data;
  476.     rbufp = __get_buf(hashp, __call_hash(hashp, kp, size), NULL, 0);
  477.     if (!rbufp)
  478.         return (ERROR);
  479.     save_bufp = rbufp;
  480.  
  481.     /* Pin the bucket chain */
  482.     rbufp->flags |= BUF_PIN;
  483.     for (bp = (u_int16_t *)rbufp->page, n = *bp++, ndx = 1; ndx < n;)
  484.         if (bp[1] >= REAL_KEY) {
  485.             /* Real key/data pair */
  486.             if (size == off - *bp &&
  487.                 memcmp(kp, rbufp->page + *bp, size) == 0)
  488.                 goto found;
  489.             off = bp[1];
  490. #ifdef HASH_STATISTICS
  491.             hash_collisions++;
  492. #endif
  493.             bp += 2;
  494.             ndx += 2;
  495.         } else if (bp[1] == OVFLPAGE) {
  496.             rbufp = __get_buf(hashp, *bp, rbufp, 0);
  497.             if (!rbufp) {
  498.                 save_bufp->flags &= ~BUF_PIN;
  499.                 return (ERROR);
  500.             }
  501.             /* FOR LOOP INIT */
  502.             bp = (u_int16_t *)rbufp->page;
  503.             n = *bp++;
  504.             ndx = 1;
  505.             off = hashp->BSIZE;
  506.         } else if (bp[1] < REAL_KEY) {
  507.             if ((ndx =
  508.                 __find_bigpair(hashp, rbufp, ndx, kp, size)) > 0)
  509.                 goto found;
  510.             if (ndx == -2) {
  511.                 bufp = rbufp;
  512.                 if (!(pageno =
  513.                     __find_last_page(hashp, &bufp))) {
  514.                     ndx = 0;
  515.                     rbufp = bufp;
  516.                     break;    /* FOR */
  517.                 }
  518.                 rbufp = __get_buf(hashp, pageno, bufp, 0);
  519.                 if (!rbufp) {
  520.                     save_bufp->flags &= ~BUF_PIN;
  521.                     return (ERROR);
  522.                 }
  523.                 /* FOR LOOP INIT */
  524.                 bp = (u_int16_t *)rbufp->page;
  525.                 n = *bp++;
  526.                 ndx = 1;
  527.                 off = hashp->BSIZE;
  528.             } else {
  529.                 save_bufp->flags &= ~BUF_PIN;
  530.                 return (ERROR);
  531.             }
  532.         }
  533.  
  534.     /* Not found */
  535.     switch (action) {
  536.     case HASH_PUT:
  537.     case HASH_PUTNEW:
  538.         if (__addel(hashp, rbufp, key, val)) {
  539.             save_bufp->flags &= ~BUF_PIN;
  540.             return (ERROR);
  541.         } else {
  542.             save_bufp->flags &= ~BUF_PIN;
  543.             return (SUCCESS);
  544.         }
  545.     case HASH_GET:
  546.     case HASH_DELETE:
  547.     default:
  548.         save_bufp->flags &= ~BUF_PIN;
  549.         return (ABNORMAL);
  550.     }
  551.  
  552. found:
  553.     switch (action) {
  554.     case HASH_PUTNEW:
  555.         save_bufp->flags &= ~BUF_PIN;
  556.         return (ABNORMAL);
  557.     case HASH_GET:
  558.         bp = (u_int16_t *)rbufp->page;
  559.         if (bp[ndx + 1] < REAL_KEY) {
  560.             if (__big_return(hashp, rbufp, ndx, val, 0))
  561.                 return (ERROR);
  562.         } else {
  563.             val->data = (u_char *)rbufp->page + (int)bp[ndx + 1];
  564.             val->size = bp[ndx] - bp[ndx + 1];
  565.         }
  566.         break;
  567.     case HASH_PUT:
  568.         if ((__delpair(hashp, rbufp, ndx)) ||
  569.             (__addel(hashp, rbufp, key, val))) {
  570.             save_bufp->flags &= ~BUF_PIN;
  571.             return (ERROR);
  572.         }
  573.         break;
  574.     case HASH_DELETE:
  575.         if (__delpair(hashp, rbufp, ndx))
  576.             return (ERROR);
  577.         break;
  578.     default:
  579.         abort();
  580.     }
  581.     save_bufp->flags &= ~BUF_PIN;
  582.     return (SUCCESS);
  583. }
  584.  
  585. static int
  586. hash_seq(dbp, key, data, flag)
  587.     const DB *dbp;
  588.     DBT *key, *data;
  589.     u_int32_t flag;
  590. {
  591.     register u_int32_t bucket;
  592.     register BUFHEAD *bufp;
  593.     HTAB *hashp;
  594.     u_int16_t *bp, ndx;
  595.  
  596.     hashp = (HTAB *)dbp->internal;
  597.     if (flag && flag != R_FIRST && flag != R_NEXT) {
  598.         hashp->errno = errno = EINVAL;
  599.         return (ERROR);
  600.     }
  601. #ifdef HASH_STATISTICS
  602.     hash_accesses++;
  603. #endif
  604.     if ((hashp->cbucket < 0) || (flag == R_FIRST)) {
  605.         hashp->cbucket = 0;
  606.         hashp->cndx = 1;
  607.         hashp->cpage = NULL;
  608.     }
  609.  
  610.     for (bp = NULL; !bp || !bp[0]; ) {
  611.         if (!(bufp = hashp->cpage)) {
  612.             for (bucket = hashp->cbucket;
  613.                 bucket <= hashp->MAX_BUCKET;
  614.                 bucket++, hashp->cndx = 1) {
  615.                 bufp = __get_buf(hashp, bucket, NULL, 0);
  616.                 if (!bufp)
  617.                     return (ERROR);
  618.                 hashp->cpage = bufp;
  619.                 bp = (u_int16_t *)bufp->page;
  620.                 if (bp[0])
  621.                     break;
  622.             }
  623.             hashp->cbucket = bucket;
  624.             if (hashp->cbucket > hashp->MAX_BUCKET) {
  625.                 hashp->cbucket = -1;
  626.                 return (ABNORMAL);
  627.             }
  628.         } else
  629.             bp = (u_int16_t *)hashp->cpage->page;
  630.  
  631. #ifdef DEBUG
  632.         assert(bp);
  633.         assert(bufp);
  634. #endif
  635.         while (bp[hashp->cndx + 1] == OVFLPAGE) {
  636.             bufp = hashp->cpage =
  637.                 __get_buf(hashp, bp[hashp->cndx], bufp, 0);
  638.             if (!bufp)
  639.                 return (ERROR);
  640.             bp = (u_int16_t *)(bufp->page);
  641.             hashp->cndx = 1;
  642.         }
  643.         if (!bp[0]) {
  644.             hashp->cpage = NULL;
  645.             ++hashp->cbucket;
  646.         }
  647.     }
  648.     ndx = hashp->cndx;
  649.     if (bp[ndx + 1] < REAL_KEY) {
  650.         if (__big_keydata(hashp, bufp, key, data, 1))
  651.             return (ERROR);
  652.     } else {
  653.         key->data = (u_char *)hashp->cpage->page + bp[ndx];
  654.         key->size = (ndx > 1 ? bp[ndx - 1] : hashp->BSIZE) - bp[ndx];
  655.         data->data = (u_char *)hashp->cpage->page + bp[ndx + 1];
  656.         data->size = bp[ndx] - bp[ndx + 1];
  657.         ndx += 2;
  658.         if (ndx > bp[0]) {
  659.             hashp->cpage = NULL;
  660.             hashp->cbucket++;
  661.             hashp->cndx = 1;
  662.         } else
  663.             hashp->cndx = ndx;
  664.     }
  665.     return (SUCCESS);
  666. }
  667.  
  668. /********************************* UTILITIES ************************/
  669.  
  670. /*
  671.  * Returns:
  672.  *     0 ==> OK
  673.  *    -1 ==> Error
  674.  */
  675. extern int
  676. __expand_table(hashp)
  677.     HTAB *hashp;
  678. {
  679.     u_int32_t old_bucket, new_bucket;
  680.     int dirsize, new_segnum, spare_ndx;
  681.  
  682. #ifdef HASH_STATISTICS
  683.     hash_expansions++;
  684. #endif
  685.     new_bucket = ++hashp->MAX_BUCKET;
  686.     old_bucket = (hashp->MAX_BUCKET & hashp->LOW_MASK);
  687.  
  688.     new_segnum = new_bucket >> hashp->SSHIFT;
  689.  
  690.     /* Check if we need a new segment */
  691.     if (new_segnum >= hashp->nsegs) {
  692.         /* Check if we need to expand directory */
  693.         if (new_segnum >= hashp->DSIZE) {
  694.             /* Reallocate directory */
  695.             dirsize = hashp->DSIZE * sizeof(SEGMENT *);
  696.             if (!hash_realloc(&hashp->dir, dirsize, dirsize << 1))
  697.                 return (-1);
  698.             hashp->DSIZE = dirsize << 1;
  699.         }
  700.         if ((hashp->dir[new_segnum] =
  701.             (SEGMENT)calloc(hashp->SGSIZE, sizeof(SEGMENT))) == NULL)
  702.             return (-1);
  703.         hashp->exsegs++;
  704.         hashp->nsegs++;
  705.     }
  706.     /*
  707.      * If the split point is increasing (MAX_BUCKET's log base 2
  708.      * * increases), we need to copy the current contents of the spare
  709.      * split bucket to the next bucket.
  710.      */
  711.     spare_ndx = __log2(hashp->MAX_BUCKET + 1);
  712.     if (spare_ndx > hashp->OVFL_POINT) {
  713.         hashp->SPARES[spare_ndx] = hashp->SPARES[hashp->OVFL_POINT];
  714.         hashp->OVFL_POINT = spare_ndx;
  715.     }
  716.  
  717.     if (new_bucket > hashp->HIGH_MASK) {
  718.         /* Starting a new doubling */
  719.         hashp->LOW_MASK = hashp->HIGH_MASK;
  720.         hashp->HIGH_MASK = new_bucket | hashp->LOW_MASK;
  721.     }
  722.     /* Relocate records to the new bucket */
  723.     return (__split_page(hashp, old_bucket, new_bucket));
  724. }
  725.  
  726. /*
  727.  * If realloc guarantees that the pointer is not destroyed if the realloc
  728.  * fails, then this routine can go away.
  729.  */
  730. static void *
  731. hash_realloc(p_ptr, oldsize, newsize)
  732.     SEGMENT **p_ptr;
  733.     int oldsize, newsize;
  734. {
  735.     register void *p;
  736.  
  737.     if (p = malloc(newsize)) {
  738.         memmove(p, *p_ptr, oldsize);
  739.         memset((char *)p + oldsize, 0, newsize - oldsize);
  740.         free(*p_ptr);
  741.         *p_ptr = p;
  742.     }
  743.     return (p);
  744. }
  745.  
  746. extern u_int32_t
  747. __call_hash(hashp, k, len)
  748.     HTAB *hashp;
  749.     char *k;
  750.     int len;
  751. {
  752.     int n, bucket;
  753.  
  754.     n = hashp->hash(k, len);
  755.     bucket = n & hashp->HIGH_MASK;
  756.     if (bucket > hashp->MAX_BUCKET)
  757.         bucket = bucket & hashp->LOW_MASK;
  758.     return (bucket);
  759. }
  760.  
  761. /*
  762.  * Allocate segment table.  On error, destroy the table and set errno.
  763.  *
  764.  * Returns 0 on success
  765.  */
  766. static int
  767. alloc_segs(hashp, nsegs)
  768.     HTAB *hashp;
  769.     int nsegs;
  770. {
  771.     register int i;
  772.     register SEGMENT store;
  773.  
  774.     int save_errno;
  775.  
  776.     if ((hashp->dir =
  777.         (SEGMENT *)calloc(hashp->DSIZE, sizeof(SEGMENT *))) == NULL) {
  778.         save_errno = errno;
  779.         (void)hdestroy(hashp);
  780.         errno = save_errno;
  781.         return (-1);
  782.     }
  783.     /* Allocate segments */
  784.     if ((store =
  785.         (SEGMENT)calloc(nsegs << hashp->SSHIFT, sizeof(SEGMENT))) == NULL) {
  786.         save_errno = errno;
  787.         (void)hdestroy(hashp);
  788.         errno = save_errno;
  789.         return (-1);
  790.     }
  791.     for (i = 0; i < nsegs; i++, hashp->nsegs++)
  792.         hashp->dir[i] = &store[i << hashp->SSHIFT];
  793.     return (0);
  794. }
  795.  
  796. #if BYTE_ORDER == LITTLE_ENDIAN
  797. /*
  798.  * Hashp->hdr needs to be byteswapped.
  799.  */
  800. static void
  801. swap_header_copy(srcp, destp)
  802.     HASHHDR *srcp, *destp;
  803. {
  804.     int i;
  805.  
  806.     P_32_COPY(srcp->magic, destp->magic);
  807.     P_32_COPY(srcp->version, destp->version);
  808.     P_32_COPY(srcp->lorder, destp->lorder);
  809.     P_32_COPY(srcp->bsize, destp->bsize);
  810.     P_32_COPY(srcp->bshift, destp->bshift);
  811.     P_32_COPY(srcp->dsize, destp->dsize);
  812.     P_32_COPY(srcp->ssize, destp->ssize);
  813.     P_32_COPY(srcp->sshift, destp->sshift);
  814.     P_32_COPY(srcp->ovfl_point, destp->ovfl_point);
  815.     P_32_COPY(srcp->last_freed, destp->last_freed);
  816.     P_32_COPY(srcp->max_bucket, destp->max_bucket);
  817.     P_32_COPY(srcp->high_mask, destp->high_mask);
  818.     P_32_COPY(srcp->low_mask, destp->low_mask);
  819.     P_32_COPY(srcp->ffactor, destp->ffactor);
  820.     P_32_COPY(srcp->nkeys, destp->nkeys);
  821.     P_32_COPY(srcp->hdrpages, destp->hdrpages);
  822.     P_32_COPY(srcp->h_charkey, destp->h_charkey);
  823.     for (i = 0; i < NCACHED; i++) {
  824.         P_32_COPY(srcp->spares[i], destp->spares[i]);
  825.         P_16_COPY(srcp->bitmaps[i], destp->bitmaps[i]);
  826.     }
  827. }
  828.  
  829. static void
  830. swap_header(hashp)
  831.     HTAB *hashp;
  832. {
  833.     HASHHDR *hdrp;
  834.     int i;
  835.  
  836.     hdrp = &hashp->hdr;
  837.  
  838.     M_32_SWAP(hdrp->magic);
  839.     M_32_SWAP(hdrp->version);
  840.     M_32_SWAP(hdrp->lorder);
  841.     M_32_SWAP(hdrp->bsize);
  842.     M_32_SWAP(hdrp->bshift);
  843.     M_32_SWAP(hdrp->dsize);
  844.     M_32_SWAP(hdrp->ssize);
  845.     M_32_SWAP(hdrp->sshift);
  846.     M_32_SWAP(hdrp->ovfl_point);
  847.     M_32_SWAP(hdrp->last_freed);
  848.     M_32_SWAP(hdrp->max_bucket);
  849.     M_32_SWAP(hdrp->high_mask);
  850.     M_32_SWAP(hdrp->low_mask);
  851.     M_32_SWAP(hdrp->ffactor);
  852.     M_32_SWAP(hdrp->nkeys);
  853.     M_32_SWAP(hdrp->hdrpages);
  854.     M_32_SWAP(hdrp->h_charkey);
  855.     for (i = 0; i < NCACHED; i++) {
  856.         M_32_SWAP(hdrp->spares[i]);
  857.         M_16_SWAP(hdrp->bitmaps[i]);
  858.     }
  859. }
  860. #endif
  861.